HPAVC/HPAVC CD-ROM.iso/ZED3DSRC.ZIP/DRAWPOLY.C

C/C++ Source or Header | 1995-06-19 | 7KB | 381 lines

#include <drawpoly.h>
#include <stdlib.h>
#include <stdio.h>



/*
 * Note: the screen coordinate system is as follows:
 *
 * O------------>x+
 * |
 * |
 * |
 * |
 * |
 * |
 * |
 * \/y+
 *
 */

void init_edges(polygon *poly, outbuffer *out)
    {
    long a;
    edge *e,*f;
    long A,B,C,D;



    e=poly->edgetable; /* e will be current edge */
    f=&e[poly->numedges-1]; /* previous edge */
    poly->nextremove=0x7fffffff; /* initialize poly->nextremove */
    /* start loop */
    for(a=0;a<poly->numedges;a++)
        {
        /* transform from projection space to buffer space */
        e->x1=proj2bufx(e->x1);
        e->y1=proj2bufy(e->y1);
        /* connect last edge to current edge */
        f->y2=e->y1;
        f->x2=e->x1;

        f=e; /* go to next edge */
        e++;
        }
    }



void sort_edges(polygon *poly, outbuffer *out)
    {
    long a,b,c,x,y,z,counter;
    edge *e, *f;

    e=poly->edgetable;
    poly->inactive.next=0; /* empty inactive edge list */

    for(counter=0;counter<poly->numedges;e++,counter++)
        {
        /* ok, for each edge... */
        /* ...sort endpoints */

        if(e->y1==e->y2)
            {
            /* RAAAAH! The dreaded edge parallel to the scanline, kill it! */
            continue;
            }

        if(e->y1>e->y2)
            {
            /* we should switch point 1 and 2 */
            b=e->x1;
            c=e->y1;
            e->x1=e->x2;
            e->y1=e->y2;
            e->x2=b;
            e->y2=c;
            }
        /* else, endpoints sorted ok */

        /* clip with top and bottom of screen */
        if(e->y1>out->maxy)
            {
            continue;
            }
        if(e->y2<-out->maxy)
            {
            continue;
            }

        if(e->y1<-out->maxy)
            {
            c=e->x1;

            e->x1=c+(e->x2-c)*(-out->maxy-e->y1)/(e->y2-e->y1);
            e->y1=-out->maxy;

            if(e->y2>out->maxy)
                {
                e->x2=c+(e->x2-c)*(out->maxy-e->y1)/(e->y2-e->y1);
                e->y2=out->maxy;
                }
            else if(e->y1==e->y2)
                {
                continue;
                }
            }
        else if(e->y2>out->maxy)
            {
            e->x2=(e->x2-e->x1)*(out->maxy-e->y1)/(e->y2-e->y1)+e->x1;
            e->y2=out->maxy;
            if(e->y1==e->y2)
                {
                continue;
                }
            }

        /* ok now, calculate slope info */
        x=e->x2-e->x1;
        y=e->y2-e->y1;

        skipit:

        if(y<0)
            {
            x=-x;
            y=-y;
            }


        e->increment=x/y;
        e->numerator=x%y;
        e->denominator=y;
        if(x<0)
            {
            /* make sure we have a positive fraction as a remainder */
            e->numerator+=y;
            e->increment-=1;
            }

        e->intercept=e->x1+out->maxx; /* initial intercept value */
        e->run=0; /* clear run */

        /* ok now, perform insertion sort based on first scanline */
        f=&poly->inactive;

        while((f->next)&&(f->next->y1<e->y1))
            f=f->next;

        /* ok insert after f */
        e->next=f->next;
        f->next=e;
        }
    /* ok inactive list is all nice and tidy now */
    }




outbuffer *allocbuf(long maxx, long maxy)
    {
    outbuffer *b;
    long s,a;

    /* allocate buffer */
    b=malloc(sizeof(outbuffer));
    if(!b) /* if malloc error */
        return 0;

    /* initialize buffer struct */
    b->maxx=maxx;
    b->maxy=maxy;
    b->width=(maxx<<1)+2;
    b->height=(maxy<<1)+1;

    /* now, we want to allocate width*(height+1) elements for both zbuffer
       and buffer */

    s=(b->height+1)*b->width; /* allocate s elements */

    b->buffer=malloc(s*sizeof(pixel));

    if(b->buffer==0)
        {
        destroybuf(b);
        return 0;
        }

    return b;
    }



void destroybuf(outbuffer *out)
    {
    if(out)
        {
        if(out->buffer)
            free(out->buffer);
        out->buffer=0;
        free(out);
        }
    }


void update_lists(polygon *poly, long scanline)
    {
    edge *e,*f,*g;
    long l;

    if(scanline>=poly->nextremove)
        /* should we remove edges? */
        {
        l=0x7fffffff; /* yes, recalculate nextremove and remove edges */
        e=&poly->active;
        f=e->next;
        while(f) /* so long as there are still edges to be examined... */
            {
            if(f->y2<=scanline)
                {
                f=f->next; /* remove edge */
                e->next=f;
                }
            else
                {
                /* keep edge, test for nextremove */
                if(e->y2<l)
                    l=e->y2; /* will be nextremove */
                e=f;
                f=f->next;
                }
            }
        poly->nextremove=l; /* store l into nextremove */
        }

    while(g=poly->inactive.next,(g)&&(g->y1==scanline))
        {
        /* as long as we need to insert new edges */
        /* recalculate nextsremove if necessary */
        if(poly->nextremove>g->y2)
            {
            poly->nextremove=g->y2;
            }

        e=&poly->active;
        f=e->next;
        while(f) /* insertion sort, most negative slope first */
            {
            if(f->intercept>=g->intercept)
                {
                if(f->intercept>g->intercept)
                    {
                    break;
                    }
                else if(f->increment>=g->increment)
                    {
                    if(f->increment>g->increment)
                        {
                        break;
                        }
                    else if(f->numerator*g->denominator>
                        g->numerator*f->denominator)
                        {
                        break;
                        }
                    }
                }
            e=f;
            f=f->next;
            }

        /* insert g after e */
        poly->inactive.next=g->next;
        g->next=f;
        e->next=g;
        }
    }



void update_intercept(polygon *poly)
    {
    edge *e;

    e=poly->active.next;

    while(e)
        {
        /* add integer part of fraction to current intercept value */
        e->intercept+=e->increment;

        /* add fractional part to running total */
        e->run+=e->numerator;
        /* is the running total at least one? */
        if(e->run>=e->denominator)
            {
            /* yes, decrease running total by one */
            e->run-=e->denominator;
            /* increase intercept value by one */
            e->intercept++;
            }

        /* next edge */
        e=e->next;
        }
    }



void draw_spans(polygon *poly, outbuffer *out, long delta)
    {
    edge *e;
    long a,b,x;
    /* start with first span */

    e=poly->active.next;
    while(e)
        {
        /* get the two endpoints of the span */
        a=e->intercept;
        e=e->next;
        b=e->intercept;
        e=e->next;

        if(b<0)
            continue;
        if(a>=out->width)
            continue;

        if(a<0)
            a=0;
        if(b>=out->width)
            b=out->width-1;

        /* blit span */
        a+=delta;
        b+=delta;
        for(x=a;x<b;x++)
            {
            out->buffer[x]=poly->color;
            }
        }
    }




void drawpolygon(polygon *poly, outbuffer *out)
    {
    long scanline,delta,mode,a;


    init_edges(poly,out);
    sort_edges(poly,out);


    if(poly->inactive.next)
        {
        /* initialize scanline to first scanline */
        scanline=poly->inactive.next->y1;

        /* calculate delta */
        delta=mulwidth(scanline+out->maxy);
        poly->active.next=0;


        /* loop until finished */
        update_lists(poly,scanline);
        while(poly->active.next)
            {
            update_intercept(poly);
            draw_spans(poly,out,delta);

            /* go to next scanline */
            scanline++;
            delta+=out->width;
            update_lists(poly,scanline);
            }
        }
    }